For almost 35 years, Sch{\"o}nhage-Strassen's algorithm has been the fastestalgorithm known for multiplying integers, with a time complexity O(n $\times$log n $\times$ log log n) for multiplying n-bit inputs. In 2007, F{\"u}rerproved that there exists K > 1 and an algorithm performing this operation inO(n $\times$ log n $\times$ K log n). Recent work by Harvey, van der Hoeven,and Lecerf showed that this complexity estimate can be improved in order to getK = 8, and conjecturally K = 4. Using an alternative algorithm, which relies onarithmetic modulo generalized Fermat primes, we obtain conjecturally the sameresult K = 4 via a careful complexity analysis in the deterministic multitapeTuring model.
展开▼
机译：在将近35年的时间里，Sch {\“ o} nhage-Strassen的算法是已知的用于整数相乘的最快算法，其时间复杂度为O（n $ \ times $ log n $ \ times $ log log n）在2007年，F {\ u}再次证明存在K> 1，并且算法在in（n $ \ times $ log n $ \ times $ K log n）中执行此操作。 Harvey，van der Hoeven和Lecerf的最新工作表明，可以改进此复杂度估计，以得到K = 8，并推测K =4。使用另一种算法，该算法依赖于算术模广义费马素数，我们推测得到相同的结果通过在确定性multitapeTuring模型中进行仔细的复杂度分析，得出K = 4。
展开▼
